package course.p7_binaryTree.s3_BSTree;

import course.p7_binaryTree.Node;

/**
 * 二叉搜索树
 * 其存储限定条件是：
 *  一个节点的左子树只能包含值小于该节点的值的节点
 *  一个节点的右子树只能包含值大于该节点的值的节点
 *  左右子树也都必须是二叉搜索树
 */
public class BSTree {

    /**
     *  插入元素
     *  基本思想是顺着树往下走，将其插入合适的位置，
     *  找个图，对着这个过程走一遍即可理解, 此树很明显不能存储相同值的节点
     * @param root 根节点
     * @param data
     * @return
     */
    Node insert(Node root , int data) {
        // 这一步很简单，就是root为空去情况
        if(root == null) {
            root = new Node();
            root.setData(data);
        } else {
            if(data < root.getData()){
                root.setLeft(insert(root.getLeft(),data));
            } else if(data > root.getData()) {
                root.setRight(insert(root.getRight(),data));
            }
        }
        return root;
    }


    /**
     *
     * 情况1： 如果待删除的元素为叶子节点，直接将其父节点的左/右 指向null 即可
     * 情况2： 如果待删除的节点有孩子节点且只有一个，只需要将其待删除节点和孩子节点设置为父亲节点的 左/右节点即可
     * 情况3： 如果待删除节点有两个孩子节点，通常的做法是从其左子树中找到最大的元素替换它，然后删除左子树的那个最大的元素即可（这个操作又对应情况1，2，3处理）
     *
     * @param root 根节点
     * @param data 待删除元素
     * @return
     */
    Node delete(Node root,int data) {
        Node temp;
        Node find = find(root,data);
        if(find==null) {
            System.out.println("没有该元素");
        }
        else {
            Node father = root;
            Node son = root;
            //找到待删除节点
            while (son != null) {
                if (data == son.getData())
                    break;
                else if (data > son.getData()) {
                    father = son;
                    son = son.getRight();
                } else {
                    father = son;
                    son = son.getLeft();
                }
            }
            // oldSon为待删除节点
            Node oldSon = son;
            //情况3
            if(son.getLeft()!=null && son.getRight()!=null) {
                temp = findMax(son.getLeft());
                son.setData(temp.getData());
                son.setLeft(delete(son.getLeft(), son.getData()));
            }
            // 情况1,2
            else {
                //情况2
                if(son.getLeft()==null)
                    son = son.getRight();
                else if(son.getRight()==null)
                    son = son.getLeft();
                // 情况1
                else son = null;

                if(father.getRight()==oldSon){
                    father.setRight(son);
                }
                else if(father.getLeft()==oldSon){
                    father.setLeft(son);
                }
            }
        }
        return root;
    }

    /**
     * 返回目标节点,查找效率高，相当于二分查找
     * @param root 二叉树根节点
     * @param data 要寻找的数据
     * @return 值等于data的节点
     */
    Node find(Node root,int data) {
        if(root==null) return null;
        while (root!=null) {
            if(data==root.getData())
                return root;
            else if(data>root.getData())
                root = root.getRight();
            else root = root.getLeft();
        }
        return null;
    }

    /**
     * 寻找树中最小元素
     * 基本思想是此树的最小元素一定在最左边
     * @param root
     * @return
     */
    Node findMin(Node root) {
        if(root==null) return null;
        while(root.getLeft()!=null)
            root = root.getLeft();
        return root;
    }

    /**
     * 寻找树中最大元素
     * 基本思想是此树的最大元素一定在最右边
     * @param root
     * @return
     */
    Node findMax(Node root) {
        if(root==null) return null;
        while(root.getRight()!=null)
            root = root.getRight();
        return root;
    }

    /**
     * 树的中序遍历(左根右)
     * 中序遍历出来的数据是有顺序的
     * @param root 根节点
     */
    public void middleTraverse(Node root) {
        if(root!=null) {
            middleTraverse(root.getLeft());
            System.out.print(root.getData()+" ");
            middleTraverse((root.getRight()));
        }
    }


}
